模拟赛题解/2025.10.17 模拟赛

T1-二分图（graph）

题面

对于一个二分图，设 $S$ 为左部点的一个非空子集，定义 $N(S)$ 为右部点与 $S$ 相邻的点的点集。

若 $|N(S)| < |S|$，则称 $S$ 是好的。

请你构造一个二分图，使得左边有 $n$ 个点，右边有 $n$ 个点，且恰好有 $k$ 个好的子集。本题每个测试包含多组输入数据，你需要分别独立处理每组数据。

$T,n\geq1,1\leq\sum n\leq 20,0\leq k<2^n$。

题解

考虑让左部点每个 $i$ 连向右部点的一个前缀 $1 \sim a_i$，满足 $a_i \leq i$ 且 $a_1 \leq a_2 \leq \cdots \leq a_n$。

此时，以 $i$ 为最大元素 $S$ 的 $|N(S)|$ 都等于 $a_i$，好的 $S$ 有 $\sum_{j \geq a_i+1} \binom{i-1}{j-1}$ 个。

从大到小考虑每个 $i$，选择最大的 $a_i$ 使 $k$ 减去最大元素为 $i$ 的方案数后 $< 2^{i-1}$，递归进入子问题。

要证明在这个过程中时刻满足 $a_{i-1} \leq a_i$。因为有 $k - \sum_{j \geq a_i+2} \binom{i-1}{j-1} \geq 2^{i-1} > k - \sum_{j \geq a_i+1} \binom{i-1}{j-1}$，所以 $k' = k - \sum_{j \geq a_i+1} \binom{i-1}{j-1} \geq 2^{i-1} - \binom{i-1}{a_i}$。而 $a_{i-1} \leq a_i$ 等价于 $k'$ 在处理到 $i-1$ 时，要求 $k' - \sum_{j \geq a_i+2} \binom{i-2}{j-1} \geq 2^{i-2}$，化简后 $2^{i-1} - \binom{i-1}{a_i} \geq 2^{i-2} + \sum_{j \geq a_i+1} \binom{i-2}{j}$，成立。

T2-乌龟与 ABC（string）

题面

乌龟正在学习英文字母。

为了训练乌龟的拼写能力，小猪给了乌龟一个由字符 A、B 和 C 组成的长度为 $n$ 的字符串 $s$。

乌龟可以对 $s$ 进行若干次操作。一次操作可以进行以下三种操作之一：

• 选择 $s$ 中的一个等于 AB 的子串，将它替换成 BA；
• 选择 $s$ 中的一个等于 BC 的子串，将它替换成 CB；
• 选择 $s$ 中的一个等于 CA 的子串，将它替换成 AC。

请你告诉乌龟他最多能进行多少次操作。

$1\leq n,\sum n\leq10^6$。

题解

字符串里的每个元素，只会和同一种字符交换。例如当交换 AB 后，别的 C 不可能到达 BA 之间，所以此时这个 A 和 B 永远不能和 C 交换。

所以要将字符串划分为若干段，每段至多包含两种字符，该段内的这两种字符进行交换。交换的最大次数即``逆序对数''。

设 $dp_i$ 表示划分完前缀 $[1, i]$ 的最大次数。可以通过维护每个 B 之前有多少个 A，以及相关前缀和，得到可以斜率优化的区间贡献的形式。

还可以更进一步，合法的转移点是 $O(1)$ 的。

每个划分断点两侧的字符都应当不同，每个相邻的段的字符集合都应当不同。对于每个 $i$，双指针维护最小的 j 满足 $[j, i]$ 只有至多两种字符，则可以划分为新一段的位置是 j 所在的极长同字符连续段的两端。

复杂度线性。

T3-跳伞（skydive）

题面

有 $n$ 个跳伞者，每个人身上系着一段由 ( 和 ) 组成的绳索——每段绳索就是一个长度为 $a_i$ 的括号串。

我们可以把这些绳索以任意顺序首尾相连，形成一根更长的绳子，然后把所有跳伞者一起从飞机上放下。绳索里每一对能“配对消失”的 ()，就是一次安全的折叠与收回。

但现在我们的目的正好相反。为了考验着陆控制，飞机故意想把绳索弄得越乱越好，于是它会把这些绳索以某种顺序连接，使得最终长绳上能被重复删除的 () 对数尽可能小。

在此前提下，我们定义长绳上能被重复删除的 () 对数为这个局面的权值。例如：

• 若长绳的串为 )(()(，局面的权值为 $1$；
• 若长绳的串为 (()))())，局面的权值为 $3$。

现在跳伞者们还不知道他们身上的绳索是什么。他们想知道，如果他们身上的绳索都是一个每一位等概率随机生成的长度为 $a_i$ 的括号串，局面的权值的期望，对 $10^9 + 7$ 取模。

题解

考虑给你 $n$ 个括号串怎么做。经过一些推导，不难发现答案是：

$$\sum_{i=1}^{n} \min(p_i, q_i) - \max_{i=1}^{n} \min(x_i, y_i)$$

其中 $p_i$ 和 $q_i$ 分别为第 $i$ 个串的左括号和右括号数量，$x_i$ 为把括号串视为网格图上的折线，起点与最低点的距离，$y_i$ 为终点与最低点的距离。

前者是容易的，枚举每个括号串有多少个左括号即可。答案为：

$$\sum_{i=1}^{n} \sum_{j=0}^{a_i} \min(j, a_i - j) \times \binom{a_i}{j} \times 2^{-a_i}$$

后者考虑拆贡献，计算：

$$\sum_{k \geq 1} P(\max_{i=1}^{n} \min(x_i, y_i) \geq k) = \sum_{k \geq 1} \left(1 - \prod_{i=1}^{n} (1 - P(\min(x_i, y_i) \geq k))\right)$$

所以我们考虑先枚举 $i, k$，对单个 $a_i$ 算 $\min(x_i, y_i) \geq k$ 的方案数。

将最低点设为 0，要求就是起点和终点都 $\geq k$。考虑枚举起点 $s, t$，终点 $t$。最低点恰好为 0 可以容斥掉，即方案数等于经过 $y = 0$ 的方案数减去经过 $y = -1$ 的方案数。

所以固定 $s, t$ 的方案数为：

$$\binom{a_i}{\frac{a_i + s + t}{2}} - \binom{a_i}{\frac{a_i + s + t + 2}{2}}$$

答案即为：

$$\sum_{s \geq k} \sum_{t \geq k} [(a_i + s + t) \mod 2 = 0] \left( \binom{a_i}{\frac{a_i + s + t}{2}} - \binom{a_i}{\frac{a_i + s + t + 2}{2}} \right)$$

发现固定 $s$ 后正负号抵消，上述式子等于：

$$\sum_{s \geq k} \binom{a_i}{\left\lfloor \frac{a_i + s + k + 1}{2} \right\rfloor}$$

这个很明显是组合数后缀和的形式。所以在最外层枚举 $i$，预处理组合数后缀和，即可 $O(1)$ 求出上述式子。

时间复杂度 $O(\sum a_i)$。

T4-乌龟与游戏（game）

题面

乌龟正在玩一款在线多人对战游戏，玩家们操控自己的角色进行较量。

假设有 $m$ 名玩家参加一场比赛，我们依次将他们编号为 1 到 $m$，第 $i$ 名玩家的角色初始体型为 $b_i$。

在游戏中，第 $i$ 名角色可以攻击第 $j$ 名角色（$i\neq j$）的条件是：$b_i - b_j\geq k$。

其中 $k$ 是比赛开始前设定的一个整数参数，可能因比赛而异。

当一次攻击发生时，第 $j$ 名角色会被淘汰，而第 $i$ 名角色会吸收它的能量，使自身的体型变为 $b_i + b_j$。

比赛会持续进行，直到场上再也没有可能的攻击为止。

如果最终只剩下一名玩家存活，则他成为本场比赛的胜者。如果存在一种攻击顺序，使得一名角色可以成为本场比赛的胜者，则称该角色是潜在赢家。

为了训练乌龟的游戏能力，小猪给了乌龟一个长为 $n$ 名玩家的初始体型，由数组 $a$ 表示。 接着，小猪向乌龟提出 $q$ 个问题，每个问题如下：

• 若选取区间 $[l, r]$ 中的角色进行一次比赛，并设比赛参数为 $k$，那么这场比赛中有多少名玩家是潜在赢家？

请你帮助乌龟解答这些问题。

$2\leq n\leq 2\times 10^5,1\leq q\leq 2\times 10^5,1\leq a_i\leq 10^9,1\leq l_i < r_i\leq n,0\leq k_i\leq 10^9$。

题解

考虑判定一个人是否能获胜。则他会每次选择生命最小的人尝试吃掉，如果不能吃掉某个人就无法获胜。

将区间按生命排序。显然一个后缀的人能够获胜，每次会吃掉的是一个前缀。每个前缀会对能够获胜的最小生命值要求有限制。

设初始的人为 $x$。对于一个 $\sum_{j \leq i} a_j - k < a_{i+1}$，要求 $i < x$。对于每个 $i < x$，要求 $\sum_{j \leq i} a_i + a_x - k \geq a_{i+1}$。暴力复杂度 $O(n^2 \log n)$。

记 $s_i = \sum_{j \leq i} a_j - k$。如果存在 $a_{i+1} > s_i$，则 $s_i$ 翻倍，只会出现 $\log V$ 次。但翻倍的性质只有 $s \geq 0$ 时存在，不过 $s < 0$ 时一定不合法，二分最小的 $i$ 使得 $s_i \geq 0$ 并从那里开始。

同理处理第二种。在 $s \geq 0$ 时处理 $\log V$ 次，但在 $s < 0$ 时的取值无法求出。记 $t_i = \sum_{j \leq i} a_j$，因为 $i = 0$ 时 $a_{i+1} \geq t_i$，所以只需要考虑 $a_{i+1} \geq t_i$ 的情况，因为 $t_i \geq 0$，只用考虑 $\log V$ 次。

主席树维护。复杂度 $O(n \log^2 V)$。